#include<bits/stdc++.h>
using namespace std;
namespace IO{
    const int BUF=1<<21;
    char buff[BUF],*p1=buff,*p2=buff;
    #define getchar() (p1==p2&&(p2=((p1=buff)+fread(buff,1,BUF,stdin)),p1==p2)?EOF:*p1++)
    template<typename T>inline void read(T &x){
        char ch=getchar();x=0;int f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        x*=f;
    }
}
using namespace IO;
const int N=5e5+5;
int n,m,k,R;
struct node{
	vector<int> f;
	int cnt;
	int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
	inline void merge(int x,int y){
		if(find(x)^find(y)){
			f[f[x]]=f[y];
			--cnt;
		}
	}
}F,G,H;
struct edge{
	int x,y;
}e[500005],P[500005];
namespace Tree{
	int top[N],sz[N],son[N],f[N],dep[N];
	vector<int> G[N];
	void dfs1(int p,int fa){
		dep[p]=dep[f[p]=fa]+1;
		for(int v:G[p])if(v^fa){
			dfs1(v,p);
			sz[p]+=sz[v];
			if(sz[v]>sz[son[p]]) son[p]=v;
		}
	}
	void dfs2(int p,int topf){
		top[p]=topf;
		if(!son[p]) return;
		dfs2(son[p],topf);
		for(int v:G[p])
			if(v!=f[p]&&v!=son[p])
				dfs2(v,v);
	}
	inline int Lca(int x,int y){
		while(top[x]^top[y]){
			if(dep[top[x]]>dep[top[y]]) x=f[top[x]];
			else y=f[top[y]];
		}return dep[x]<dep[y]?x:y;
	}
	int w[N],mx,mx1;
	void dfs3(int p){
		for(int v:G[p])
			if(v^f[p]) dfs3(v),w[p]+=w[v];
		if(w[p]>mx) mx1=mx,mx=w[p];
		else mx1=max(mx1,w[p]);
	}
	inline void sol(){
		for(int i=1;i<=m;++i) G[e[i].x].push_back(e[i].y),G[e[i].y].push_back(e[i].x);
		dfs1(1,0);
		dfs2(1,1);
		for(int i=1;i<=k;++i){
			int lc=Lca(P[i].x,P[i].y);
			++w[P[i].x],++w[P[i].y];
			w[lc]-=2;
		}
		dfs3(1);
		if(R==0) puts("0");
		else if(R==1) printf("%d\n",mx);
		else printf("%d\n",mx+mx1);
		exit(0);
	}
}
int main(){
	freopen("hide.in","r",stdin);
	freopen("hide.out","w",stdout);
	read(n),read(m),read(k),read(R);
	for(int i=1;i<=m;++i) read(e[i].x),read(e[i].y);
	for(int i=1;i<=k;++i) read(P[i].x),read(P[i].y);
	if(m==n-1) return Tree::sol(),0;
	F.f.resize(n+1);
	G.f.resize(n+1);
	H.f.resize(n+1);
	for(int i=1;i<=n;++i) G.f[i]=i;
	G.cnt=n;
	if(R==0){
		puts("0");
		return 0;
	}
	if(R==1){
		int ans=0;
		const int lim=min(m,(int)4e8/max(m,k));
		for(int i=1;i<=lim;++i){
			F=G;
			int sum=0;
			for(int j=i+1;j<=m;++j) F.f[F.find(e[j].x)]=F.find(e[j].y);
			for(int j=1;j<=k;++j) sum+=(F.find(P[j].x)!=F.find(P[j].y));
			ans=max(ans,sum);
			F.merge(e[i].x,e[i].y);
		}
		printf("%lld\n",ans);
		return 0;
	}
	const int lim=min(m,(int)6.5e8/m/max(m,k));
	int ans=0;
	for(int i=1;i<=lim&&G.cnt>1;++i){
		F=G;
		for(int j=i+1;j<=m&&F.cnt>1;++j){
			H=F;
			for(int l=j+1;l<=m&&H.cnt>1;++l) H.merge(e[l].x,e[l].y);
			if(H.cnt<=1) break;
			int kk;
			if(H.find(e[i].x)==H.find(e[j].x)||H.find(e[i].x)==H.find(e[j].y)) kk=H.find(e[i].x);
			else kk=H.find(e[i].y);
			int sum=0;
			for(int l=1;l<=k;++l){
				if(H.find(P[l].x)==H.find(P[l].y)) continue;
				if(H.cnt==2){
					sum+=(H.find(P[l].x)!=H.find(P[l].y));
					continue;
				}
				if(H.f[P[l].x]==kk||H.f[P[l].y]==kk) ++sum;
				else sum+=2;
			}
			ans=max(ans,sum);
			F.merge(e[j].x,e[j].y);
		}
		G.merge(e[i].x,e[i].y);
	}
	printf("%d\n",ans);
	return 0;
}

